{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "<center>\n",
    "<img src=\"https://github.com/Yorko/mlcourse.ai/blob/master/img/ods_stickers.jpg?raw=true\" />\n",
    "<br>    \n",
    "\n",
    "\n",
    "<div style=\"font-weight:700;font-size:25px\"> [mlcourse.ai](https://mlcourse.ai) - Open Machine Learning Course </div>\n",
    "\n",
    "<br>\n",
    "\n",
    "Auteur: [Alexey Natekin](https://www.linkedin.com/in/natekin/), fondateur d’OpenDataScience, Machine Learning Evangelist. Traduit et édité par [Olga Daykhovskaya](https://www.linkedin.com/in/odaykhovskaya/), [Anastasia Manokhina](https://www.linkedin.com/in/anastasiamanokhina/), [Egor Polusmak](https://www.linkedin.com/in/egor-polusmak/), [Yuanyuan Pao](https://www.linkedin.com/in/yuanyuanpao/) et [Ousmane Cissé](https://github.com/oussou-dev). Ce matériel est soumis aux termes et conditions de la licence [Creative Commons CC BY-NC-SA 4.0](https://creativecommons.org/licenses/by-nc-sa/4.0/). L'utilisation gratuite est autorisée à des fins non commerciales."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "<center> \n",
    "    \n",
    "<div style=\"font-weight:700;font-size:25px\"> Thème 10. Gradient Boosting </div>\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "<img src='https://habrastorage.org/web/4a9/edb/082/4a9edb082408442ea47a12b75f19d122.jpg' align='right' width=40%>\n",
    "\n",
    "Jusqu'à présent, nous avons couvert 9 sujets allant de l'analyse exploratoire de données à l'analyse de séries chronologiques en Python:\n",
    "<spoiler title=\"List of the series' articles\">\n",
    "1. [Analyse exploratoire de données avec Pandas](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-1-exploratory-data-analysis-with-pandas-de57880f1a68)\n",
    "2. [Visualisation de données avec Python](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-2-visual-data-analysis-in-python-846b989675cd)\n",
    "3. [Classification, arbres-de-décision et k plus proches voisins](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-3-classification-decision-trees-and-k-nearest-neighbors-8613c6b6d2cd)\n",
    "4. [Classification linéaire et régression](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-4-linear-classification-and-regression-44a41b9b5220)\n",
    "5. [Bagging et random forest](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-5-ensemble-of-algorithms-and-random-forest-8e05246cbba7)\n",
    "6. [Feature Engineering and Feature Selection](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-6-feature-engineering-and-feature-selection-8b94f870706a)\n",
    "7. [Apprentissage non supervisé : (ACP) Analyse en Composantes Principales et Clustering](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-7-unsupervised-learning-pca-and-clustering -db7879568417)\n",
    "8. [Vowpal Wabbit : Learning with Gigabytes of Data](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-8-vowpal-wabbit-fast-learning-with-gigabytes-of-data-60f750086237)\n",
    "9. [Analyse des séries temporelles en Python](https://medium.com/open-machine-learning-course/open-machine-learning-course-topic-9-time-series-analysis-in-python-a270cb05e0b3)\n",
    "\n",
    "Aujourd'hui, nous allons examiner l'un des algorithmes d'apprentissage automatique les plus populaires et les plus pratiques : le Gradient Boosting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "<div style=\"font-weight:700;font-size:20px\"> Sommaire de l'article </div>\n",
    "\n",
    "\n",
    "Nous vous recommandons de lire cet article dans l’ordre décrit ci-dessous, mais n'hésitez pas à parcourir les différentes sections."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "toc": true
   },
   "source": [
    "<h1><span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#1.-Introduction-et-histoire-du-Boosting\" data-toc-modified-id=\"1.-Introduction-et-histoire-du-Boosting-1\">1. Introduction et histoire du Boosting</a></span><ul class=\"toc-item\"><li><span><a href=\"#Histoire-de-la-GBM\" data-toc-modified-id=\"Histoire-de-la-GBM-1.1\">Histoire de la GBM</a></span></li></ul></li><li><span><a href=\"#2.-L'algorithme-GBM\" data-toc-modified-id=\"2.-L'algorithme-GBM-2\">2. L'algorithme GBM</a></span><ul class=\"toc-item\"><li><ul class=\"toc-item\"><li><span><a href=\"#Problème\" data-toc-modified-id=\"Problème-2.0.1\">Problème</a></span></li><li><span><a href=\"#Descente-de-gradient-fonctionnel\" data-toc-modified-id=\"Descente-de-gradient-fonctionnel-2.0.2\">Descente de gradient fonctionnel</a></span></li><li><span><a href=\"#L'algorithme-GBM-classique-de-Friedman\" data-toc-modified-id=\"L'algorithme-GBM-classique-de-Friedman-2.0.3\">L'algorithme GBM classique de Friedman</a></span></li><li><span><a href=\"#Exemple-pas-à-pas:-comment-fonctionne-la-GBM\" data-toc-modified-id=\"Exemple-pas-à-pas:-comment-fonctionne-la-GBM-2.0.4\">Exemple pas à pas: comment fonctionne la GBM</a></span></li></ul></li></ul></li><li><span><a href=\"#3.-Fonctions-de-perte\" data-toc-modified-id=\"3.-Fonctions-de-perte-3\">3. Fonctions de perte</a></span><ul class=\"toc-item\"><li><ul class=\"toc-item\"><li><span><a href=\"#Fonctions-de-perte-liées-à-la--régression\" data-toc-modified-id=\"Fonctions-de-perte-liées-à-la--régression-3.0.1\">Fonctions de perte liées à la  régression</a></span></li><li><span><a href=\"#Fonctions-de-perte-de-classification\" data-toc-modified-id=\"Fonctions-de-perte-de-classification-3.0.2\">Fonctions de perte de classification</a></span></li><li><span><a href=\"#Poids\" data-toc-modified-id=\"Poids-3.0.3\">Poids</a></span></li></ul></li></ul></li><li><span><a href=\"#4.-Conclusion\" data-toc-modified-id=\"4.-Conclusion-4\">4. Conclusion</a></span></li><li><span><a href=\"#5.-Mission-de-démonstration\" data-toc-modified-id=\"5.-Mission-de-démonstration-5\">5. Mission de démonstration</a></span></li><li><span><a href=\"#6.-Ressources-utiles\" data-toc-modified-id=\"6.-Ressources-utiles-6\">6. Ressources utiles</a></span></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "# 1. Introduction et histoire du Boosting\n",
    "Presque tout le monde en dans le domaine de l'apprentissage automatique a entendu parler du Gradient boosting. Nombreux data scientist incluent cet algorithme dans leur boîte à outils en raison des bons résultats obtenus sur tout problème (inconnu) donné.\n",
    "\n",
    "De plus, XGBoost est souvent la recette standard pour [gagner](https://github.com/dmlc/xgboost/blob/master/demo/README.md#usecases) les cmpétitions de [ML](http://blog.kaggle.com/tag/xgboost/). Il est si populaire que l’idée de superposer des XGBoosts est devenue un mème. De plus, le boosting est un composant important dans [de nombreux systèmes de recommandation](https://en.wikipedia.org/wiki/Learning_to_rank#Practical_usage_by_search_engines); parfois, il est même considérée comme une [marque](https://yandex.com/company/technologies/matrixnet/).\n",
    "Penchons-nous sur l'histoire et le développement du boosting."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "Le boosting est né de [la question :](http://www.cis.upenn.edu/~mkearns/papers/boostnote.pdf) est-il possible d'obtenir un modèle fort à partir d'un grand nombre de modèles relativement faibles et simples ? Par «modèles faibles», nous n'entendons pas de simples modèles de base tels que les arbres de décision, mais des modèles avec des performances de précision médiocres, où médiocre est un peu meilleur que le hasard.\n",
    "\n",
    "[Une réponse mathématique positive](http://www.cs.princeton.edu/~schapire/papers/strengthofweak.pdf) a été identifiée, mais il a fallu quelques années pour développer des algorithmes pleinement fonctionnels basés sur cette solution, par exemple AdaBoost. Ces algorithmes adoptent une approche dite \"gourmande\" : ils construisent d’abord une combinaison linéaire de modèles simples (algorithmes de base) en repesant les données d’entrée. Ensuite, le modèle (généralement un arbre de décision) est construit sur des objets précédemment prédits de manière incorrecte, auxquels des pondérations plus importantes ont été attribuées.\n",
    "\n",
    "<spoiler title=\"More about AdaBoost\">\n",
    "De nombreux cours d'apprentissage automatique étudient AdaBoost - l'ancêtre du GBM (Gradient Boosting Machine). Cependant, depuis la fusion d'AdaBoost avec GBM, il est devenu évident qu'AdaBoost n'est qu'une variante particulière de GBM.\n",
    "\n",
    "L'algorithme lui-même a une interprétation visuelle très claire et une intuition permettant de définir des poids. Jetons un coup d'œil au problème de classification des jouets suivant dans lequel nous allons scinder les données entre les arbres de profondeur 1 (également appelés «stumps») à chaque itération d'AdaBoost. Pour les deux premières itérations, nous avons l'image suivante :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "<img src='https://habrastorage.org/web/d28/78f/7ba/d2878f7bad0340fc8002e5ba6d0879a5.jpg' width=70%>\n",
    "\n",
    "La taille du point correspond à son poids, attribué à une prédiction incorrecte. À chaque itération, nous pouvons constater que ces poids augmentent - les \"stumps\" ne peuvent pas faire face à ce problème. Cependant, si nous votons (de manière pondérée) pour les \"stumps\", nous obtiendrons les bonnes classifications :\n",
    "\n",
    "<img src='https://habrastorage.org/web/b2b/029/d89/b2b029d898f64bbbb158e15d29595969.png' width=70%>\n",
    "\n",
    "Pseudocode:\n",
    "- Initialiser les poids des échantillons $\\Large w_i^{(0)} = \\frac{1}{l}, i = 1, \\dots, l$.\n",
    "- pour tout $t = 1, \\dots, T$\n",
    "    * Entraînez l'algo $\\Large b_t$, laissez $\\epsilon_t$ être l’erreur d’entraînement.\n",
    "    * $\\Large \\alpha_t = \\frac{1}{2}ln\\frac{1 - \\epsilon_t}{\\epsilon_t}$.\n",
    "    * Mettez à jour les poids des échantillons : $\\Large w_i^{(t)} = w_i^{(t-1)} e^{-\\alpha_t y_i b_t(x_i)}, i = 1, \\dots, l$.\n",
    "    * Normaliser les poids des échantillons: $\\Large w_0^{(t)} = \\sum_{j = 1}^k w_j^{(t)}, w_i^{(t)} = \\frac{w_i^{(t)}}{w_0^{(t)}}, i = 1, \\dots, l$.\n",
    "- Retourne $\\sum_t^{T}\\alpha_tb_t$\n",
    "\n",
    "\n",
    "[Voici](https://www.youtube.com/watch?v=k4G2VCuOMMg) un exemple plus détaillé d'AdaBoost où, en itérant, nous pouvons voir que les poids augmentent, en particulier à la frontière entre les classes.\n",
    "\n",
    "AdaBoost fonctionne bien, mais [le manque](https://www.cs.princeton.edu/courses/archive/spring07/cos424/papers/boosting-survey.pdf) d'explication de la raison de la réussite de l'algorithme a semé le doute. Certains considéraient cela comme un super-algorithme, une solution miracle, mais d'autres étaient sceptiques et pensaient qu'AdaBoost était juste trop bien sur-appris\n",
    "\n",
    "Le problème de sur-apprentissage existait bel et bien, surtout lorsque les données présentaient de fortes valeurs aberrantes. Par conséquent, dans ce type de problème, AdaBoost était instable. Heureusement, quelques professeurs du département de statistique de Stanford, qui avaient créé Lasso, Elastic Net et Random Forest, ont commencé à étudier l'algorithme. En 1999, Jerome Friedman a proposé la généralisation du développement d’algorithmes de Boosting - Gradient Boosting (Machine), également connu sous le nom de GBM. Avec ce travail, Friedman a mis en place la base statistique de nombreux algorithmes fournissant l'approche générale du Boosting pour l'optimisation dans l'espace fonctionnel.\n",
    "\n",
    "CART, bootstrap, et beaucoup d'autres algorithmes sont issus du département des statistiques de Stanford. Ce faisant, leurs noms seront introduits dans les prochains manuels. Ces algorithmes sont très pratiques et certains travaux récents ne sont pas encore largement adoptés. Par exemple, consultez [glinternet](https://arxiv.org/abs/1308.2719).\n",
    "\n",
    "Pas beaucoup d'enregistrements vidéo de Friedman sont disponibles. Bien qu'il y ait une très intéressante [interview](https://www.youtube.com/watch?v=8hupHmBVvb0) avec lui sur la création de CART et sur la façon dont ils ont résolu les problèmes de statistiques (similaires à la data analysis et à la data science aujourd'hui) il y a plus de 40 ans.\n",
    "\n",
    "Il existe également une excellente [conférence](https://www.youtube.com/watch?v=zBk3PK3g-Fc) de Hastie, une rétrospective sur l'analyse de données fournie par l'un des créateurs des méthodes que nous utilisons tous les jours.\n",
    "\n",
    "En général, la recherche en ingénierie et en algorithmes est passée d'une approche à part entière à la construction et à l'étude d'algorithmes. D'un point de vue mathématique, il ne s'agit pas d'un gros changement : nous ajoutons (ou renforçons) des algorithmes faibles et élargissons notre ensemble avec des améliorations progressives pour les parties des données où le modèle était inexact. Mais, cette fois, le prochain modèle simple ne repose pas uniquement sur des objets repondérés, mais améliore son approximation du gradient de la fonction objective globale. Ce concept ouvre grandement nos algorithmes à l'imagination et aux extensions.\n",
    "\n",
    "<img src=\"https://habrastorage.org/webt/h2/v4/k9/h2v4k9r-4yn4jwvwz99fbss4ghi.png\" />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "## Histoire de la GBM\n",
    "\n",
    "Plus de 10 ans après l’introduction de la GBM, celle-ci est devenue un élément essentiel de la boîte à outils de la science des données.\n",
    "GBM a été étendu pour s’appliquer à différents problèmes statistiques : GLMboost et GAMboost pour renforcer les modèles GAM existants, CoxBoost pour les courbes de survie et RankBoost et LambdaMART pour le classement.\n",
    "De nombreuses réalisations de GBM sont également apparues sous différents noms et sur différentes plateformes : GBM stochastique, GBDT (arbres de décision boostés par gradient), GBRT (arbres de régression boostés par gradient), MART (arbres de régression additive multiples), etc. En outre, la communauté du ML (Machine Learning) était très segmentée et dissociée, ce qui rendait difficile de savoir à quel point la stimulation était devenue généralisée.\n",
    "\n",
    "Dans le même temps, le boosting avait été activement utilisé dans le classement des recherches. Ce problème a été réécrit en termes de fonction de perte qui pénalise les erreurs dans l'ordre de sortie. Il est donc devenu pratique de l'insérer simplement dans la GBM. AltaVista a été l’une des premières entreprises à introduire le renforcement du classement. Bientôt, les idées se répandent dans Yahoo, Yandex, Bing, etc. Une fois que cela s'est produit, le boosting est devenu l'un des principaux algorithmes utilisés non seulement dans la recherche, mais également dans les technologies de base de l'industrie.\n",
    "\n",
    "Les compétitions <img src='https://habrastorage.org/web/48a/ea4/fff/48aea4fffdbe4e5f9205ba81110e6061.jpg' align='right' width=30%> ML, en particulier Kaggle, ont joué un rôle majeur dans la popularisation du Boosting. À présent, les chercheurs disposaient d’une plate-forme commune leur permettant de faire face à différents problèmes de science des données avec un grand nombre de participants du monde entier. Avec Kaggle, il est possible de tester de nouveaux algorithmes sur les données réelles, ce qui permet aux algorithmes de \"briller\", et de fournir des informations complètes sur le partage des résultats de performance de modèle entre jeux de données de compétition. C’est exactement ce qui est arrivé avec le Boosting quand il a été utilisé chez [Kaggle](http://blog.kaggle.com/2011/12/21/score-xavier-conort-on-coming-second-in-give-me-some-credit/) (voir les entretiens avec les gagnants de Kaggle à partir de 2011 qui ont principalement utilisé le boosting). La bibliothèque [XGBoost](https://github.com/dmlc/xgboost) a rapidement gagné en popularité après son apparition. XGBoost n'est pas un nouvel algorithme unique. il s'agit simplement d'une réalisation extrêmement efficace de la GBM classique avec des heuristiques supplémentaires.\n",
    "\n",
    "Cet algorithme a suivi le chemin très typique des algorithmes ML aujourd'hui : problème mathématique et savoir-faire algorithmique pour des applications pratiques réussies et une adoption en masse des années après sa première apparition."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "# 2. L'algorithme GBM\n",
    "### Problème\n",
    "\n",
    "Nous allons résoudre le problème de l'approximation des fonctions dans un contexte d'apprentissage supervisé général. Nous avons un ensemble de fonctionnalités $ \\large x $ et les variables cibles $\\large y, \\large \\left\\{ (x_i, y_i) \\right\\}_{i=1, \\ldots,n}$ que nous utilisons pour restaurer la dépendance $\\large y = f(x) $. Nous restaurons la dépendance en approximant $ \\large \\hat{f}(x) $ et en comprenant quelle approximation est la meilleure lorsque nous utilisons la fonction de perte $ \\large L(y,f) $, que nous voulons minimiser: $ \\large y \\approx \\hat{f}(x), \\large \\hat{f}(x) = \\underset{f(x)}{\\arg\\min} \\ L(y,f(x)) $.\n",
    "\n",
    "<img src='https://github.com/Yorko/mlcourse.ai/blob/master/img/topic10_help_with_func.png?raw=true'  align='center'>\n",
    "\n",
    "Pour le moment, nous ne faisons aucune hypothèse concernant le type de dépendance $ \\large f(x) $, le modèle de notre approximation $ \\large \\hat{f}(x) $ ou la distribution de la variable cible $ \\large y $. Nous nous attendons seulement à ce que la fonction $ \\large L(y,f) $ soit différentiable. Notre approche est très générale : nous définissons $ \\large \\hat {f}(x) $ en minimisant la perte :\n",
    "$$ \\large  \\hat{f}(x) = \\underset{f(x)}{\\arg\\min} \\ \\mathbb {E} _{x,y}[L(y,f(x))]  $$\n",
    "\n",
    "Malheureusement, le nombre de fonctions $ \\large f(x) $ n'est pas simplement grand, mais son espace fonctionnel est infiniment dimensionnel. C'est pourquoi il est acceptable pour nous de limiter l'espace de recherche par une famille de fonctions $ \\large f(x, \\theta), \\theta \\in \\mathbb{R}^d $. Cela simplifie beaucoup l'objectif car nous avons maintenant une optimisation solvable des valeurs de paramètres:\n",
    "$ \\large \\hat{f}(x) = f(x, \\hat{\\theta}),$\n",
    "$$\\large \\hat{\\theta} = \\underset{\\theta}{\\arg\\min} \\ \\mathbb {E} _{x,y}[L(y,f(x,\\theta))] $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "Des solutions analytiques simples pour trouver les paramètres optimaux $ \\large \\hat{\\theta} $ n'existant souvent pas, les paramètres sont généralement approximés de manière itérative. Pour commencer, nous écrivons la fonction de perte empirique $ \\large L_{\\theta}(\\hat{\\theta}) $ qui nous permettra d’évaluer nos paramètres en utilisant nos données. De plus, écrivons notre approximation $ \\large \\hat{\\theta} $ pour un certain nombre d'itérations $ \\large M $ sous forme de somme:\n",
    "$ \\large \\hat{\\theta} = \\sum_{i = 1}^M \\hat{\\theta_i}, \\\\\n",
    "\\large L_{\\theta}(\\hat{\\theta}) =  \\sum_{i = 1}^N L(y_i,f(x_i, \\hat{\\theta}))$\n",
    "\n",
    "Ensuite, il ne reste plus qu'à trouver un algorithme itératif approprié pour minimiser $\\large L_{\\theta}(\\hat{\\theta})$. La descente de gradient est l'option la plus simple et la plus fréquemment utilisée. Nous définissons le gradient comme étant $\\large \\nabla L_{\\theta}(\\hat{\\theta})$ et y ajoutons nos évaluations itératives $\\large \\hat{\\theta_i}$ (puisque nous minimisons la perte, nous ajoutons le signe moins). Notre dernière étape consiste à initialiser notre première approximation $\\large \\hat{\\theta_0}$ et à choisir le nombre d'itérations $\\large M$. Passons en revue les étapes de cet algorithme inefficace et naïf pour approximer $\\large \\hat{\\theta}$:\n",
    "\n",
    "1. Définir l'approximation initiale des paramètres $\\large \\hat{\\theta} = \\hat{\\theta_0}$\n",
    "2. Pour chaque itération $\\large t = 1, \\dots, M$, répétez les étapes 3 à 7:\n",
    "3. Calculer le gradient de la fonction de perte $\\large \\nabla L_{\\theta}(\\hat{\\theta})$ pour l'approximation courante $\\large \\hat{\\theta}$\n",
    "$\\large \\nabla L_{\\theta}(\\hat{\\theta}) = \\left[\\frac{\\partial L(y, f(x, \\theta))}{\\partial \\theta}\\right]_{\\theta = \\hat{\\theta}}$\n",
    "4. Définir l'approximation itérative actuelle $\\large \\hat{\\theta_t}$ en fonction du gradient calculé\n",
    "$\\large \\hat{\\theta_t} \\leftarrow −\\nabla L_{\\theta}(\\hat{\\theta})$\n",
    "5. Mettre à jour l'approximation des paramètres $\\large \\hat{\\theta}$:\n",
    "$\\large \\hat{\\theta} \\leftarrow \\hat{\\theta} + \\hat{\\theta_t} = \\sum_{i = 0}^t \\hat{\\theta_i} $\n",
    "6. Enregistrer le résultat de l'approximation $\\large \\hat{\\theta}$:\n",
    "$\\large \\hat{\\theta} = \\sum_{i = 0}^M \\hat{\\theta_i} $\n",
    "7. Utiliser la fonction trouvée $\\large \\hat{f}(x) = f(x, \\hat{\\theta})$\n",
    "\n",
    "<img src='https://habrastorage.org/web/2b5/5d6/90d/2b55d690d99e4ec0976b360aae6ce4df.jpg'   align='center'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### Descente de gradient fonctionnel\n",
    "\n",
    "Imaginons une seconde que nous puissions améliorer l'optimisation dans l'espace des fonctions et rechercher de manière itérative les approximations $\\large \\hat{f}(x)$ en tant que fonctions elles-mêmes. Nous allons exprimer notre approximation comme une somme d'améliorations incrémentales, chacune étant une fonction. Pour plus de commodité, nous commencerons immédiatement par la somme de l'approximation initiale $\\large \\hat{f_0}(x)$:\n",
    "$$\\large \\hat{f}(x) = \\sum_{i = 0}^M \\hat{f_i}(x)$$\n",
    "\n",
    "Rien n'est encore arrivé. nous avons seulement décidé de chercher notre approximation $\\large \\hat{f}(x)$ non pas comme un grand modèle avec beaucoup de paramètres (par exemple, un réseau de neurones), mais comme une somme de fonctions prétendant que nous nous déplaçons dans un espace fonctionnel.\n",
    "\n",
    "Afin d'accomplir cette tâche, nous devons limiter notre recherche à une famille de fonctions $\\large \\hat{f}(x) = h(x, \\theta)$. Il y a quelques problèmes ici - tout d’abord, la somme des modèles peut être plus compliquée que n’importe quel modèle de cette famille; Deuxièmement, l'objectif général est toujours dans l'espace fonctionnel. Notons qu'à chaque étape, nous devrons choisir un coefficient optimal $\\large \\rho \\in \\mathbb{R}$. Pour l'étape $\\large t$, le problème est le suivant:\n",
    "$$\\large \\hat{f}(x) = \\sum_{i = 0}^{t-1} \\hat{f_i}(x), \\\\\n",
    "\\large (\\rho_t,\\theta_t) = \\underset{\\rho,\\theta}{\\arg\\min} \\ \\mathbb {E} _{x,y}[L(y,\\hat{f}(x) +  \\rho \\cdot h(x, \\theta))], \\\\\n",
    "\\large \\hat{f_t}(x) = \\rho_t \\cdot h(x, \\theta_t)$$\n",
    "\n",
    "C'est ici que la magie opère. Nous avons défini tous nos objectifs en termes généraux, comme si nous pouvions former tout type de modèle $\\large h(x, \\theta)$ pour n’importe quel type de fonction de perte $\\large L(y, f(x, \\theta))$. En pratique, c'est extrêmement difficile, mais heureusement, il existe un moyen simple de résoudre ce problème.\n",
    "\n",
    "Connaissant l'expression du gradient de la fonction de perte, nous pouvons calculer sa valeur sur nos données. Donc, entraînons les modèles de telle sorte que nos prédictions soient davantage corrélées à ce gradient (avec un signe moins). En d'autres termes, nous allons utiliser les moindres carrés pour corriger les prédictions avec ces résidus. Pour les tâches de classification, de régression et de classement, nous minimiserons la différence quadratique entre les pseudo-résidus $\\large r$ et nos prédictions. Pour l'étape $\\large t$, le problème final se présente comme suit:\n",
    "$$ \\large \\hat{f}(x) = \\sum_{i = 0}^{t-1} \\hat{f_i}(x), \\\\\n",
    "\\large r_{it} = -\\left[\\frac{\\partial L(y_i, f(x_i))}{\\partial f(x_i)}\\right]_{f(x)=\\hat{f}(x)}, \\quad \\mbox{for } i=1,\\ldots,n ,\\\\\n",
    "\\large \\theta_t = \\underset{\\theta}{\\arg\\min} \\ \\sum_{i = 1}^{n} (r_{it} - h(x_i, \\theta))^2, \\\\\n",
    "\\large \\rho_t = \\underset{\\rho}{\\arg\\min} \\ \\sum_{i = 1}^{n} L(y_i, \\hat{f}(x_i) + \\rho \\cdot h(x_i, \\theta_t))$$\n",
    "\n",
    "<img src='https://github.com/Yorko/mlcourse.ai/blob/master/img/topic10_regression_for_everybody.jpg?raw=true'   align='center' width=60%>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### L'algorithme GBM classique de Friedman\n",
    "\n",
    "Nous pouvons maintenant définir l’algorithme GBM classique proposé par Jerome Friedman en 1999. C’est un algorithme supervisé qui a les composants suivants:\n",
    "\n",
    "- ensemble de données $\\large \\left\\{ (x_i, y_i) \\right\\}_{i=1, \\ldots,n}$;\n",
    "- nombre d'itérations $\\large M$;\n",
    "- choix de la fonction de perte $\\large L(y, f)$ avec un gradient défini;\n",
    "- choix de la famille de fonctions des algorithmes de base $\\large h(x, \\theta)$ avec la procédure d'apprentissage;\n",
    "- hyperparamètres supplémentaires $\\large h(x, \\theta)$ (par exemple, dans les arbres de décision, la profondeur de l’arbre);\n",
    "\n",
    "La seule chose qui reste est l'approximation initiale $\\large f_0(x)$. Pour simplifier, pour une approximation initiale, une valeur constante $\\large \\gamma$ est utilisée. La valeur constante, ainsi que le coefficient optimal $\\large \\rho $, sont identifiés via une recherche binaire ou un autre algorithme de recherche de ligne sur la fonction de perte initiale (et non un gradient). Nous avons donc notre algorithme GBM décrit comme suit:\n",
    "\n",
    "1. Initialiser GBM avec une valeur constante $\\large \\hat{f}(x) = \\hat{f}_0, \\hat{f}_0 = \\gamma,  \\gamma \\in \\mathbb{R}$\n",
    "$\\large \\hat{f}_0 = \\underset{\\gamma}{\\arg\\min} \\ \\sum_{i = 1}^{n} L(y_i, \\gamma)$\n",
    "2. Pour chaque itération $\\large t = 1, \\dots, M$, répéter :\n",
    "3. Calculer les pseudo-résidus $\\large r_t$\n",
    "$\\large r_{it} = -\\left[\\frac{\\partial L(y_i, f(x_i))}{\\partial f(x_i)}\\right]_{f(x)=\\hat{f}(x)}, \\quad \\mbox{for } i=1,\\ldots,n$\n",
    "4. Construire le nouvel algorithme de base $\\large h_t(x)$ sous forme de régression sur les pseudo-résidus $\\large \\left\\{ (x_i, r_{it}) \\right\\}_{i=1, \\ldots,n}$\n",
    "5. Trouver le coefficient optimal $\\large \\rho_t $ à $\\large h_t(x)$ concernant la fonction de perte initiale\n",
    "$\\large \\rho_t = \\underset{\\rho}{\\arg\\min} \\ \\sum_{i = 1}^{n} L(y_i, \\hat{f}(x_i) +  \\rho \\cdot h(x_i, \\theta))$\n",
    "6. Enregistrer $\\large \\hat{f_t}(x) = \\rho_t \\cdot h_t(x)$\n",
    "7. Mettre à jour l'approximation courante $\\large \\hat{f}(x)$\n",
    "$\\large \\hat{f}(x) \\leftarrow \\hat{f}(x) + \\hat{f_t}(x) = \\sum_{i = 0}^{t} \\hat{f_i}(x)$\n",
    "8. Composez le mrdèle final GBM $\\large \\hat{f}(x)$\n",
    "$\\large \\hat{f}(x) = \\sum_{i = 0}^M \\hat{f_i}(x) $\n",
    "9. Conquérir Kaggle et le reste du monde"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### Exemple pas à pas: comment fonctionne la GBM\n",
    "\n",
    "Voyons un exemple du fonctionnement de la GBM. Dans cet exemple de basé sur un jeu, nous allons restaurer une fonction bruyante $\\large y = cos(x) + \\epsilon, \\epsilon \\sim \\mathcal{N}(0, \\frac{1}{5}), x \\in [-5,5]$.\n",
    "\n",
    "<img src='https://habrastorage.org/web/9fe/04d/7ba/9fe04d7ba5a645d49fc6aa3e875c8c41.jpg'   align='center'>\n",
    "\n",
    "Il s’agit d’un problème de régression avec une cible à valeur réelle. Nous allons donc choisir d’utiliser la fonction de perte d’erreur quadratique moyenne. Nous allons générer 300 paires d'observations et les approximer avec des arbres de décision de profondeur 2. Réunissons tout ce dont nous avons besoin pour utiliser GBM:\n",
    "- Jeu de données $\\large \\left\\{ (x_i, y_i) \\right\\}_{i=1, \\ldots,300}$ ✓\n",
    "- Nombre d'itérations $\\large M = 3$ ✓;\n",
    "- La fonction de perte d'erreur quadratique moyenne $\\large L(y, f) = (y-f)^2$ ✓\n",
    "- Le gradient de perte en $\\large L(y, f) = L_2$ n'est que des résidus $\\large r = (y - f)$ ✓;\n",
    "- Arbre de décision en tant qu'algorithme de base $\\large h(x)$ ✓;\n",
    "- Hyperparamètres des arbres de décision : la profondeur des arbres est égale à 2 ✓;\n",
    "\n",
    "Pour l'erreur quadratique moyenne, l'initialisation $\\large \\gamma$ et les coefficients $\\large \\rho_t$ sont simples. Nous initialiserons GBM avec la valeur moyenne $\\large \\gamma = \\frac{1}{n} \\cdot \\sum_{i = 1}^n y_i$ et définirons tous les coefficients $\\large \\rho_t$ sur 1.\n",
    "\n",
    "Nous allons lancer GBM et dessiner deux types de graphes : l’approximation courante $\\large \\hat{f}(x)$ (graphe bleu) et chaque arbre $\\large \\hat{f_t}(x)$ construit sur ses pseudo-résidus (graphe vert). Le numéro du graphique correspond au numéro d'itération :\n",
    "\n",
    "<img src='https://habrastorage.org/web/edb/328/98a/edb32898ad014d8d95782759d11f63fb.png'   align='center'>\n",
    "\n",
    "À la deuxième itération, nos arbres ont retrouvé la forme de base de la fonction. Cependant, à la première itération, nous voyons que l'algorithme n'a construit que la \"branche gauche\" de la fonction ($\\large x \\in [-5, -4]$). Cela était dû au fait que nos arbres n’avaient tout simplement pas assez de profondeur pour construire une branche symétrique à la fois et qu’ils se concentraient sur la branche gauche présentant l’erreur la plus grande. Par conséquent, la branche de droite n'est apparue qu'après la deuxième itération.\n",
    "\n",
    "Le reste du processus se déroule comme prévu : à chaque étape, nos pseudo-résidus ont diminué et GBM a amélioré de mieux en mieux la fonction d'origine à chaque itération. Cependant, par construction, les arbres ne peuvent pas se rapprocher d'une fonction continue, ce qui signifie que GBM n'est pas idéal dans cet exemple. Pour jouer avec les approximations de fonctions GBM, vous pouvez utiliser la démo interactive impressionnante de ce blog intitulée [Brilliantly wrong](http://arogozhnikov.github.io/2016/06/24/gradient_boosting_explained.html) :\n",
    "\n",
    "<img src='https://habrastorage.org/web/779/3e0/e66/7793e0e66b7d4871b6391a94cd5d4cf2.jpg'   align='center'>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "# 3. Fonctions de perte\n",
    "\n",
    "Si nous voulons résoudre un problème de classification au lieu d'une régression, qu'est-ce qui changerait ? Il suffit de choisir une fonction de perte appropriée, $\\large L(y, f)$. C’est le moment le plus important qui détermine exactement comment nous allons optimiser et à quelles caractéristiques nous pouvons nous attendre dans le modèle final.\n",
    "\n",
    "En règle générale, nous n'avons pas besoin de l'inventer nous-mêmes : les chercheurs l'ont déjà fait pour nous. Aujourd'hui, nous allons explorer les fonctions de perte pour les deux objectifs les plus courants : la régression $\\large y \\in \\mathbb{R}$ et la classification binaire $\\large y \\in \\left\\{-1, 1\\right\\}$.\n",
    "\n",
    "### Fonctions de perte liées à la  régression\n",
    "\n",
    "Commençons par un problème de régression pour $\\large y \\in \\mathbb{R}$. Afin de choisir la fonction de perte appropriée, nous devons déterminer quelles propriétés de la distribution conditionnelle $\\large (y|x)$ nous souhaitons restaurer. Les options les plus courantes sont:\n",
    "\n",
    "- $\\large L(y, f) = (y - f)^2$ a.k.a. $\\large L_2$ perte ou perte gaussienne. C'est la moyenne conditionnelle classique, qui est le cas le plus simple et le plus courant. Si nous n'avons pas d'informations supplémentaires ou d'exigences pour qu'un modèle soit robuste, nous pouvons utiliser la perte gaussienne.\n",
    "- perte $\\large L_1$ ou $\\large L_1$ ou perte laplacienne. Au premier abord, cette fonction ne semble pas pouvoir être différenciée, mais définit en réalité la médiane conditionnelle. Comme nous le savons, la médiane est robuste aux valeurs aberrantes, raison pour laquelle cette fonction de perte est meilleure dans certains cas. La pénalité pour les grandes variations n’est pas aussi lourde que dans $\\large L_2$.\n",
    "- $ \\large \\begin{equation}  L(y, f) =\\left\\{   \\begin{array}{@{}ll@{}}     (1 - \\alpha) \\cdot |y - f|, & \\text{if}\\ y-f \\leq 0 \\\\     \\alpha \\cdot |y - f|, & \\text{if}\\ y-f >0  \\end{array}\\right. \\end{equation}, \\alpha \\in (0,1)\n",
    "$ a.k.a. $\\large L_q$ perte ou perte de Quantile. Au lieu de la médiane, il utilise des quantiles. Par exemple, $\\large \\alpha = 0.75$ correspond au 75%-quantile. Nous pouvons voir que cette fonction est asymétrique et pénalise les observations qui se trouvent du côté droit du quantile défini.\n",
    "\n",
    "<img src='https://habrastorage.org/web/6d5/e3a/09c/6d5e3a09c703491b947fde851e412ac0.png' width=60%>\n",
    "\n",
    "Utilisons la fonction de perte $\\large L_q$ sur nos données. L'objectif est de restaurer le quantile conditionnel de cosinus à 75%. Mettons tout en œuvre pour GBM:\n",
    "- Jeu de données $\\large \\left\\{ (x_i, y_i) \\right\\}_{i=1, \\ldots,300}$ ✓\n",
    "- Un nombre d'itérations $\\large M = 3$ ✓;\n",
    "- Fonction de perte pour les quantiles $ \\large \\begin{equation}   L_{0.75}(y, f) =\\left\\{\n",
    "\\begin{array}{@{}ll@{}}    0.25 \\cdot |y - f|, & \\text{if}\\ y-f \\leq 0 \\\\     0.75 \\cdot |y - f|, & \\text{if}\\ y-f >0   \\end{array}\\right. \\end{equation} $ ✓;\n",
    "- Gradient $\\large L_{0.75}(y, f)$ - fonction pondérée par $\\large \\alpha = 0.75$. Nous allons former un modèle basé sur des arbres pour la classification :\n",
    "$\\large r_{i} = -\\left[\\frac{\\partial L(y_i, f(x_i))}{\\partial f(x_i)}\\right]_{f(x)=\\hat{f}(x)} = $\n",
    "$\\large = \\alpha I(y_i > \\hat{f}(x_i) ) - (1 - \\alpha)I(y_i \\leq \\hat{f}(x_i) ), \\quad \\mbox{for } i=1,\\ldots,300$ ✓;\n",
    "- Arbre de décision en tant qu'algorithme de base $\\large h(x)$ ✓;\n",
    "- Hyperparamètre des arbres : profondeur = 2 ✓;\n",
    "\n",
    "Pour notre approximation initiale, nous prendrons le quantile nécessaire de $\\large y$. Cependant, nous ne savons rien des coefficients optimaux $\\large \\rho_t$, nous allons donc utiliser la recherche par ligne standard. Les résultats sont les suivants :\n",
    "\n",
    "<img src='https://habrastorage.org/web/0e6/7dd/614/0e67dd614076499e91c8c4238457ae4d.png'   align='center'>\n",
    "\n",
    "Nous pouvons observer que, à chaque itération, $\\large r_{i} $ ne prend que 2 valeurs possibles, mais GBM est toujours capable de restaurer notre fonction initiale.\n",
    "\n",
    "Les résultats globaux de GBM avec fonction de perte quantile sont les mêmes que les résultats avec fonction de perte quadratique décalée par $\\large \\approx 0.135$. Mais si nous utilisions le 90%-quantile, nous n'aurions pas assez de données car les classes seraient déséquilibrées. Nous devons nous en souvenir lorsque nous traitons des problèmes non standard.\n",
    "\n",
    "*\"Quelques mots sur les fonctions de perte de régression\"*\n",
    "\n",
    "Pour les tâches de régression, de nombreuses fonctions de perte ont été développées, certaines avec des propriétés supplémentaires. Par exemple, ils peuvent être robustes, comme dans la [fonction de perte de Huber](https://en.wikipedia.org/wiki/Huber_loss). Pour un petit nombre de valeurs aberrantes, la fonction de perte fonctionne comme $\\large L_2$, mais après un seuil défini, la fonction devient $\\large L_1$. Cela permet de réduire l'effet des valeurs aberrantes et de se concentrer sur l'image globale.\n",
    "\n",
    "Nous pouvons illustrer cela avec l'exemple suivant. Les données sont générées à partir de la fonction $\\large y = \\frac{sin(x)}{x}$ avec ajout de bruit, un mélange de distributions normales et de distributions de Bernulli. Nous montrons les fonctions sur les graphes A-D et le GBM correspondant sur F-H (le graphe E représente la fonction initiale):\n",
    "\n",
    "<img src='https://habrastorage.org/web/130/05b/222/13005b222e8a4eb68c3936216c05e276.jpg'   align='center'> [Taille originale](https://habrastorage.org/web/130/05b/222/13005b222e8a4eb68c3936216c05e276.jpg).\n",
    "\n",
    "\n",
    "Dans cet exemple, nous avons utilisé des splines comme algorithme de base. Vous voyez, il ne faut pas toujours que ce soit des arbres pour le Bosting ?\n",
    "\n",
    "Nous pouvons clairement voir la différence entre les fonctions $\\large L_2$, $\\large L_1$ et la perte de Huber. Si nous choisissons des paramètres optimaux pour la perte de Huber, nous pouvons obtenir la meilleure approximation possible parmi toutes nos options. La différence est également visible dans les quantiles de 10%, 50% et 90%.\n",
    "\n",
    "Malheureusement, la fonction de perte de Huber n’est prise en charge que par très peu de bibliothèques / packages populaires; h2o le supporte, mais pas XGBoost. Il est pertinent pour d'autres choses plus exotiques comme les [expectiles conditionnelles](https://www.slideshare.net/charthur/quantile-and-expectile-regression), mais il peut quand même s'agir de connaissances intéressantes.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### Fonctions de perte de classification\n",
    "\n",
    "Maintenant, regardons le problème de classification binaire $\\large y \\in \\left\\{-1, 1\\right\\}$. Nous avons vu que GBM peut même optimiser des fonctions de perte non différenciables. Techniquement, il est possible de résoudre ce problème avec une perte de régression $\\large L_2$, mais ce ne serait pas correct.\n",
    "\n",
    "La distribution de la variable cible nécessite que nous utilisions un \"log-likehood\", il nous faut donc différentes fonctions de perte pour les cibles multipliées par leurs prédictions : $\\large y \\cdot f$. Les choix les plus courants seraient les suivants: \n",
    "\n",
    "- $\\large L(y, f) = log(1 + exp(-2yf))$ ak.a. Perte logistique ou perte de Bernoulli. Cela a une propriété intéressante qui pénalise même les classes correctement prédites, ce qui aide non seulement à optimiser la perte, mais également à écarter davantage les classes, même si toutes les classes sont correctement prédites.\n",
    "- perte de $\\large L(y, f) = exp(-yf)$ a.k.a. AdaBoost. Le classique AdaBoost est équivalent à GBM avec cette fonction de perte. Conceptuellement, cette fonction est très similaire à la perte logistique, mais elle est plus pénalisée de façon exponentielle si la prédiction est fausse.\n",
    "\n",
    "<img src='https://habrastorage.org/web/bf5/9de/dcf/bf59dedcfd9d49b18e89ce342b09ce69.png' width=60%>\n",
    "\n",
    "Générons un nouveau jeu de données pour notre problème de classification. En guise de base, nous prendrons notre cosinus \"bruyant\" et nous utiliserons la fonction de signe pour les classes de la variable cible. Nos données ressemblent à ceci (le \"jitter-noise\" est ajouté pour plus de clarté) :\n",
    "\n",
    "<img src='https://habrastorage.org/web/e72/513/78b/e7251378bf6d459ab1aeea7a1f1996a1.jpg'>\n",
    "\n",
    "\n",
    "Nous utiliserons la perte logistique pour rechercher ce que nous améliorons réellement. Donc, encore une fois, nous avons mis en place ce que nous allons utiliser pour GBM :\n",
    "- jeu de données $\\large \\left\\{ (x_i, y_i) \\right\\}_{i=1, \\ldots,300}, y_i \\in \\left\\{-1, 1\\right\\}$ ✓\n",
    "- Nombre d'itérations $\\large M = 3$ ✓;\n",
    "- Perte logistique en tant que fonction de perte, son gradient est calculé de la manière suivante :\n",
    "$\\large r_{i} = \\frac{2 \\cdot y_i}{1 + exp(2 \\cdot y_i \\cdot \\hat{f}(x_i)) }, \\quad \\mbox{for } i=1,\\ldots,300$ ✓;\n",
    "- Arbre de décision en tant qu'algorithme de base $\\large h(x)$ ✓;\n",
    "- Hyperparamètres des arbres de décision : la profondeur de l'arbre est égale à 2 ✓;\n",
    "\n",
    "Cette fois, l'initialisation de l'algorithme est un peu plus difficile. Premièrement, nos classes sont déséquilibrées (63% contre 37%). Deuxièmement, il n’existe pas de formule analytique connue pour l’initialisation de notre fonction de perte, nous devons donc rechercher $\\large \\hat{f_0} = \\gamma$ via search :\n",
    "\n",
    "<img src='https://habrastorage.org/web/f8a/054/702/f8a05470271448d9bc0d4dc3e524a571.png' width=60%>\n",
    "\n",
    "\n",
    "Notre approximation initiale optimale est d'environ -0,273. Vous auriez pu deviner que c'était négatif car il est plus rentable de tout prédire comme la classe la plus populaire, mais il n'y a pas de formule pour la valeur exacte. Maintenant, commençons enfin par GBM, et regardons ce qui se passe réellement sous le capot: \n",
    "\n",
    "<img src='https://habrastorage.org/web/7b4/ab0/5fa/7b4ab05fa0a543bfad94950e47f91568.png'   align='center'>\n",
    "\n",
    "L'algorithme a restauré avec succès la séparation entre nos classes. Vous pouvez voir comment les zones \"inférieures\" se séparent car les arbres sont plus confiants dans la prédiction correcte de la classe négative et comment se forment les deux étapes des classes mixtes. Il est clair que nous avons beaucoup d'observations correctement classées et un certain nombre d'observations avec des erreurs importantes qui sont apparues en raison du bruit dans les données."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "### Poids\n",
    "\n",
    "Parfois, nous voulons une fonction de perte plus spécifique pour notre problème. Par exemple, dans les séries chronologiques financières, il se peut que nous souhaitions accorder plus de poids aux mouvements importants dans la série chronologique; pour la prévision du taux de désabonnement, il est plus utile de prédire le désabonnement des clients ayant un LTV élevé (ou une valeur à vie: combien d'argent un client rapportera-t-il à l'avenir ?). \n",
    "\n",
    "<img src='https://habrastorage.org/web/0c0/ad0/3a4/0c0ad03a4c4b46bfa5bcd5101678c9c4.jpg'   align='center'>\n",
    "\n",
    "Le guerrier statistique inventerait sa propre fonction de perte, en écrivant le gradient (pour un entraînement plus efficace, incluez le Hessian) et vérifierait avec soin si cette fonction remplissait les propriétés requises. Cependant, il y a de fortes chances que quelqu'un commette une erreur quelque part, se heurte à des difficultés de calcul et consacre une quantité excessive de temps à la recherche.\n",
    "\n",
    "Au lieu de cela, un instrument très simple a été inventé (ce dont on se souvient rarement dans la pratique) : peser des observations et attribuer des fonctions de pondération. L'exemple le plus simple d'une telle pondération est la définition de pondérations pour la balance de classes. En général, si nous savons qu'un sous-ensemble de données, tant dans les variables d'entrée $\\large x$ que dans la variable cible $\\large y$, a une plus grande importance pour notre modèle, nous leur attribuons simplement une pondération plus importante, $\\large w(x,y)$. L’objectif principal est de satisfaire aux exigences générales en matière de poids: \n",
    "$$ \\large w_i \\in \\mathbb{R}, \\\\\n",
    "\\large w_i \\geq 0 \\quad \\mbox{for } i=1,\\ldots,n, \\\\\n",
    "\\large \\sum_{i = 1}^n w_i > 0 $$\n",
    "\n",
    "Les poids peuvent réduire considérablement le temps passé à ajuster la fonction de perte à la tâche que nous résolvons et encourager les expériences sur les propriétés des modèles cibles. L'attribution de ces poids est entièrement fonction de la créativité. Nous ajoutons simplement des poids scalaires:\n",
    "$$ \\large L_{w}(y,f) = w \\cdot L(y,f), \\\\\n",
    "\\large r_{it} =   - w_i \\cdot \\left[\\frac{\\partial L(y_i, f(x_i))}{\\partial f(x_i)}\\right]_{f(x)=\\hat{f}(x)}, \\quad \\mbox{for } i=1,\\ldots,n$$\n",
    "\n",
    "Il est clair que, pour les poids arbitraires, nous ne connaissons pas les propriétés statistiques de notre modèle. Lier les poids aux valeurs $\\large y$ peut souvent être trop compliqué. Par exemple, l'utilisation de poids proportionnels à $\\large |y|$ dans la fonction de perte $\\large L_1$ n'est pas équivalente à la perte de $\\large L_2$ car le gradient ne prendra pas en compte les valeurs des prédictions elles-mêmes : $\\large \\hat{f}(x)$.\n",
    "\n",
    "Nous mentionnons tout cela afin de mieux comprendre nos possibilités. Créons des poids très exotiques pour notre jeu de données. Nous allons définir une fonction de poids fortement asymétrique comme suit :\n",
    "$$ \\large \\begin{equation} w(x) =\\left\\{   \\begin{array}{@{}ll@{}}     0.1, & \\text{if}\\ x \\leq 0 \\\\     0.1 + |cos(x)|, & \\text{if}\\ x >0 \\end{array}\\right. \\end{equation} $$\n",
    "\n",
    "<img src='https://habrastorage.org/web/8c2/1b1/aa4/8c21b1aa47134f7aa46b15ef910369b2.png'   align='center'>\n",
    "\n",
    "Avec ces poids, nous nous attendons à obtenir deux propriétés : moins de détails pour les valeurs négatives de $\\large x$ et la forme de la fonction, similaire au cosinus initial. Nous reprenons les réglages des autres GBM de notre exemple précédent avec une classification incluant la recherche par ligne pour les coefficients optimaux. Regardons ce que nous avons :\n",
    "\n",
    "<img src='https://habrastorage.org/web/afc/cca/72a/afccca72a0774990b685de37b0fe9d9f.png'   align='center'>\n",
    "\n",
    "Nous avons atteint le résultat escompté. Premièrement, nous pouvons voir à quel point les pseudo-résidus diffèrent fortement; à l'itération initiale, ils ressemblent presque au cosinus d'origine. Deuxièmement, la partie gauche du graphique de la fonction était souvent ignorée au profit de la droite, qui avait des poids plus importants. Troisièmement, la fonction que nous avons obtenue à la troisième itération a reçu suffisamment d’attention et a commencé à ressembler au cosinus original (elle a également légèrement sur-appris)\n",
    "\n",
    "Les poids sont un outil puissant mais risqué que nous pouvons utiliser pour contrôler les propriétés de notre modèle. Si vous souhaitez optimiser votre fonction de perte, essayez d'abord de résoudre un problème plus simple en ajoutant des pondérations aux observations, à votre discrétion."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "# 4. Conclusion\n",
    "\n",
    "Aujourd'hui, nous avons appris la théorie derrière le Gradient Boosting. GBM n'est pas seulement un algorithme spécifique, mais une méthodologie commune pour la construction d'ensembles de modèles. De plus, cette méthodologie est suffisamment flexible et extensible - il est possible de former un grand nombre de modèles en tenant compte de différentes fonctions de perte avec une variété de fonctions de pondération.\n",
    "\n",
    "La pratique et les compétitions ML montrent que, dans les problèmes classiques (à l’exception des images, de l’audio et des données très éparses), la GBM est souvent l’algorithme le plus efficace (pour ne pas mentionner les ensembles superposés et de haut niveau, où la GBM fait presque toujours partie intégrante). En outre, il existe de nombreuses adaptations de GBM [pour l'apprentissage par renforcement](https://arxiv.org/abs/1603.04119) (Minecraft, ICML 2016). En passant, l'algorithme Viola-Jones, qui est encore utilisé en vision par ordinateur, est basé sur [AdaBoost](https://en.wikipedia.org/wiki/Viola%E2%80%93Jones_object_detection_framework#Learning_algorithm).\n",
    "\n",
    "Dans cet article, nous avons volontairement omis de poser des questions sur la régularisation, la stochasticité et les hyper-paramètres de GBM. Ce n'est pas par hasard que nous avons utilisé un petit nombre d'itérations $\\large M = 3$. Si nous utilisions 30 arbres au lieu de 3 et formions le GBM comme décrit, le résultat ne serait pas prévisible :\n",
    "\n",
    "<img src='https://github.com/Yorko/mlcourse.ai/blob/master/img/topic10_good_fit.png?raw=true'   align='center' width=60%>\n",
    "<img src='https://github.com/Yorko/mlcourse.ai/blob/master/img/topic10_overfitting.png?raw=true'   align='center' width=60%>\n",
    "\n",
    "\n",
    "<img src='https://habrastorage.org/web/27f/0f5/3be/27f0f53be9424cb1afaffb9a0e32909f.jpg' align='center'>\n",
    "\n",
    "[Démo interactive](http://arogozhnikov.github.io/2016/07/05/gradient_boosting_playground.html)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "lang": "fr"
   },
   "source": [
    "# 5. Mission de démonstration\n",
    "Votre tâche consiste à battre les bases de référence dans le cadre de la compétition \"Flight delays\" de [Kaggle Inclass](https://www.kaggle.com/c/flight-delays-fall-2018). Vous recevez un [démarreur CatBoost](https://www.kaggle.com/kashnitsky/mlcourse-ai-fall-2019-catboost-starter), l'astuce consiste à proposer de bonnes caractéristiques (features).\n",
    "\n",
    "# 6. Ressources utiles\n",
    "- Liste des cours [site](https://mlcourse.ai), [course repo](https://github.com/Yorko/mlcourse.ai), and YouTube [channel](https://www.youtube.com/watch?v=QKTuw4PNOsU&list=PLVlY_7IJCMJeRfZ68eVfEcu-UcN9BbwiX)\n",
    "- Course materials as a [Kaggle Dataset](https://www.kaggle.com/kashnitsky/mlcourse)\n",
    "- mlcourse.ai lectures on gradient boosting: [theory](https://youtu.be/g0ZOtzZqdqk) and [practice](https://youtu.be/V5158Oug4W8)\n",
    "- [Original article](https://statweb.stanford.edu/~jhf/ftp/trebst.pdf) about GBM from Jerome Friedman\n",
    "- “Gradient boosting machines, a tutorial”, [paper](https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3885826/) by Alexey Natekin, and Alois Knoll\n",
    "- [Chapter in Elements of Statistical Learning](http://statweb.stanford.edu/~tibs/ElemStatLearn/printings/ESLII_print10.pdf) from Hastie, Tibshirani, Friedman (page 337)\n",
    "- [Wiki](https://en.wikipedia.org/wiki/Gradient_boosting) article about Gradient Boosting\n",
    "- [Introduction to boosted trees (Xgboost docs)](https://xgboost.readthedocs.io/en/latest/tutorials/model.html)\n",
    "- [Video-lecture by Hastie](https://www.youtube.com/watch?v=wPqtzj5VZus) about GBM at h2o.ai conference\n",
    "- [CatBoost vs. Light GBM vs. XGBoost](https://towardsdatascience.com/catboost-vs-light-gbm-vs-xgboost-5f93620723db) on \"Towards Data Science\"\n",
    "- [Benchmarking and Optimization of\n",
    "Gradient Boosting Decision Tree Algorithms](https://arxiv.org/abs/1809.04559), [XGBoost: Scalable GPU Accelerated Learning](https://arxiv.org/abs/1806.11248) - benchmarking CatBoost, Light GBM, and XGBoost (no 100% winner)"
   ]
  }
 ],
 "metadata": {
  "hide_input": false,
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.4"
  },
  "nbTranslate": {
   "displayLangs": [
    "*"
   ],
   "hotkey": "alt-t",
   "langInMainMenu": true,
   "sourceLang": "en",
   "targetLang": "fr",
   "useGoogleTranslate": true
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "",
   "title_sidebar": "Contents",
   "toc_cell": true,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
